package com.celan.year2023.month01.day06;

import java.util.*;
import java.util.concurrent.TimeUnit;

public class Solution {
    public int countEven(int num) {
        int cnt = 0;
        for (int i = num; i > 1; i--) {
            int sum = 0;
            for (char c : String.valueOf(i).toCharArray()) {
                sum += (c - '0');
            }
            if (sum % 2 == 0) cnt++;
        }
        return cnt;
    }

    public class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
            next = null;
        }
    }

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) return null;
        ListNode curA = headA;
        ListNode curB = headB;
        while (curA != curB) {
            if (curA == null) curA = headB;
            else curA = curA.next;
            if (curB == null) curB = headA;
            else curB = curB.next;
        }
        return curA;
    }

    public int rob(int[] nums) {
        if (nums.length == 0) return 0;
        if (nums.length == 1) return nums[0];

        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);

        for (int i = 2; i < nums.length; i++) {
            dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
        }

        return dp[nums.length - 1];
    }

    List<List<Integer>> dic = new ArrayList<>();
    int[] flags;

    public boolean canFinish(int numCourses, int[][] prerequisites) {
        flags = new int[numCourses];
        for (int i = 0; i < numCourses; i++) {
            dic.add(new ArrayList<>());
        }
        for (int[] cp : prerequisites)
            dic.get(cp[0]).add(cp[1]);
        for (int i = 0; i < numCourses; i++) {
            if (!dfs(i)) return false;
        }
        return true;
    }

    private boolean dfs(int idx) {
        if (flags[idx] == 1) return false;
        if (flags[idx] == -1) return true;

        flags[idx] = 1;
        for (int i : dic.get(idx)) {
            if (!dfs(i)) return false;
        }
        flags[idx] = -1;
        return true;
    }

}


